package com.zhj.structure.graph.utils;

import com.zhj.structure.linear.utils.MyQueue;
import com.zhj.structure.linear.utils.MyStack;

/**
 * @PackageName:com.zhj.structure.figure.utils
 * @ClassName:Graph
 * @auter: 朱慧杰
 * @date:2020/8/12 0012 21:54
 **/
public class Graph {

    private Vertex[] vertices;
    private int currentSize;
    private int[][] adjMat;
    private MyStack stack = new MyStack();
    private MyQueue queue = new MyQueue();
    private int currentIndex;

    public Graph(int size) {
        vertices = new Vertex[size];
        adjMat = new int[size][size];
    }

    /**
     * 添加顶点
     * @param v
     */
    public void addVertex(Vertex v) {
        adjMat[currentSize][currentSize] = 1;
        vertices[currentSize++] = v;
    }

    public void addEdge(String v1,String v2) {
        int index1 = 0;
        int index2 = 0;
        for (int i = 0; i < vertices.length; i++) {
            if (vertices[i].getValue().equals(v1)) {
                index1 = i;
                break;
            }
        }
        for (int i = 0; i < vertices.length; i++) {
            if (vertices[i].getValue().equals(v2)) {
                index2 = i;
                break;
            }
        }
        adjMat[index1][index2] = 1;
        adjMat[index2][index1] = 1;
    }

    public int[][] getAdjMat() {
        return adjMat;
    }

    /**
     * 深度优先算法
     */
    public void dfs() {
        // 把第0个标记已访问状态
        vertices[0].setVisited(true);
        // 将下标压入
        stack.push(0);
        System.out.println(vertices[0].getValue());
        // 遍历
        out:while (!stack.isEmpty()) {
            for (int i = currentIndex+1; i < vertices.length; i++) {
                if (adjMat[currentIndex][i] == 1 && vertices[i].isVisited() == false) {
                    stack.push(i);
                    vertices[i].setVisited(true);
                    System.out.println(vertices[i].getValue());
                    continue out;
                }
            }
            // 弹出栈顶元素
            stack.pop();
            if (!stack.isEmpty()) {
                currentIndex = stack.peek();
            }
        }
    }

    /**
     * 广度优先算法
     */
    public void bfs() {
        // 把第0个标记已访问状态
        vertices[0].setVisited(true);
        // 将下标压入
        queue.add(0);
        System.out.println(vertices[0].getValue());

    }
}
